package com.code.test.first.greedy;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.md
 * <p>
 * 给定一个非负整数数组，你最初位于数组的第一个位置。
 * <p>
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * <p>
 * 判断你是否能够到达最后一个位置。
 * <p>
 * 示例  1:
 * <p>
 * 输入: [2,3,1,1,4]
 * 输出: true
 * 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
 * 示例  2:
 * <p>
 * 输入: [3,2,1,0,4]
 * 输出: false
 * 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
 */
public class Code55 {

    public static void main(String[] args) {
//        int[] nums = {2, 4, 5, 3, 1, 0, 6};
        int[] nums = {3,2,1,0,4};
        boolean ret = maxProfit(nums);
        System.out.println(ret);
    }

    /**
     * 当前数组元素的值代表可跳跃步数，把跳几步转换为最大跳跃范围，因为意味着在可选范围内，是可以到达最后一个，即为可达
     * 如果最大范围怎么跳都不超过，即为不可达
     *
     *
     * 刚看到本题一开始可能想：当前位置元素如果是 3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？
     *
     * 其实跳几步无所谓，关键在于可跳的覆盖范围！
     *
     * 不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。
     *
     * 这个范围内，别管是怎么跳的，反正一定可以跳过来。
     *
     * 那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！
     *
     * 每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
     *
     * 贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
     *
     * 局部最优推出全局最优，找不出反例，试试贪心！
     */
    public static boolean maxProfit(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            //最大可达范围 = 当前数值 + 当前索引下标
            maxReach = Math.max(maxReach, i + nums[i]);
            //如果最大可达范围超过数组最后一个，即可达
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}
